This invention relates to the field of logic systems. More particularly, the present invention is directed to methods and logic apparatus for image interpolation.
Good quality interpolation of digitally encoded images to higher resolution is important in many applications of digital imaging. Such applications include image zooming for digital camera pre-print processing or image zooming in digital video. Image up-scaling interpolation is commonly performed by simple methods such as pixel replication, bilinear interpolation, or spline interpolation [1,2]. The visual results of these interpolation methods suffer from blurring and aliasing affects.
Adaptive interpolation is one method used to achieve better results in image up-scaling. While digital imaging applications require the ability to scale an image to any fractional scaling ratio, most existing adaptive interpolation methods are designed for an integer scaling ratio only. Another typical problem with many advanced interpolation methods is their high computational complexity and high storage complexity.
Adaptive interpolation algorithms have been developed to improve the magnified image quality. Allebach et al. [4] and Biancardi et al. [5] use an interpolation technique that is directed by a high resolution edge-map that was generated from the original low resolution image. Thurnhofer et al. [6] and Michaud et al. [7] used interpolation method that first find the local edge orientation and then interpolate along the edge direction that was found. This method was also being used by Ting et al. [3] for interpolating along sharply curved edges.
A review of interpolation methods was conducted during development of the present invention. A number of papers were reviewed. Reviewed methods include the following approaches:
1. Conventional interpolation methods that use a constant convolution kernel;
2. Adaptive methods that use edge information for the interpolation;
3. Interpolation methods that use Median filters;
4. Interpolation methods that use image transformation like DCT;
5. Interpolation methods that exploit video motion compensation.
Ting. et al. [3] discusses using local gradient properties for interpolating the image. The discussed method consists of two phases. In the first phase, the method interpolates the image using a fuzzy logic system with member functions that are Gaussian-like, depending on calculated gradients of the source image. In its second phase, the method changes values on sharply curved edges due to unsatisfying performance of the first phase along such edges. These values are replaced by linear interpolation along the sharply curved edges detected. The complexity of the edge detection discussed by Ting is high and is not suitable for fractional scaling ratios. The method used by the first phase fails when a fractional scale ratio is needed. Its behavior with a fractional scale ratio is very close to pixel replication, due to the properties of the Gaussian function.
While the first phase of the interpolation algorithm in Ting uses an interpolation formula that is gradient dependent, the formula does not produce consistent satisfactory results and Ting therefore uses a second correction phase that requires much higher complexity.
Paint Shop Pro 5, a very well-known graphics program, uses three methods of resizing: smart size, Bilinear resample, and Bicubic resample. The first method is a special resizing algorithm of Paint Shop Pro and the other two are classical methods. None of these methods yield consistently satisfactory results.
What is needed is a method or apparatus for performing image interpolation that is suitable for lower complexity applications and produces results with a minimum of visual artifacts. What is further needed is a method that can be made adaptive and that can use a non-integer scaling ratio.
Sobel Operator Background
A variety of different operators and functions are known and used in the art to perform various image processing tasks. Specific operators are given herein for the sake of clarity of the description of the invention, however other known or yet to be developed operators and functions may also be used to generate gradients and other values used by the invention.
One important operator is known as the Sobel Operator. In its ideal form, the operator consists of a pair of 3xc3x973 convolution kernel masks, one as shown in (5) and the other rotated by 90xc2x0.
These kernels are designed to respond maximally to edges running vertically and horizontally relative to the pixel grid, one kernel for each of the two perpendicular orientations. The kernels can be applied separately to the input image, to produce separate measurements of the gradient component in each orientation (call these Gx and Gy). The components can then be combined to determine an absolute magnitude of the gradient at each point and the orientation of that gradient. The gradient magnitude is given by: |G|=sqrt(Gx2+Gy2). In many applications, an approximate magnitude for the gradient is computed using: |G|=(|Gx|+|Gy|)/2, which is much faster to compute.
Often, the absolute magnitude is the only output a user from a Sobel operationxe2x80x94the two components of the gradient are conveniently computed and added in a single pass over the input image using a pseudo-convolution operator as shown below:
Using this kernel, the approximate magnitude can be obtained from: |Gai|=(|(P1+2P2+P3)xe2x88x92(P7+2P8+P9)|+|(P3+2P6+P9)xe2x88x92(P1+2P4+P7)|)/2.
The angle of orientation of the edge (relative to the pixel grid) giving rise to the spatial gradient is given by: xcex8=arctan Gy/Gx. In this case, orientation angle value 0 is taken to mean that the direction of maximum contrast from black to white runs from left to right on the image, and other angles are measured anti-clockwise from this.
A related operator is the Prewitt gradient edge detector. This works in a very similar way to the Sobel operator but uses slightly different kernels. These kernels produce similar results to the Sobel, but the operator is not as isotropic in its response. Another known operator is the Roberts operator.
Image Interpolation
As is known in the art, common applications for pixel interpolation include changing the size of a digital image or changing the resolution of a digital image. In either case, generally the number of pixels in the image will change and the final size of the digital image will be related to the final pixel size. When the number of pixels in an image increases, either due to increasing the size or the resolution of the original image, that is often referred to in the art as upscaling.
It is also known in the art that pixels can be roughly square, as is common for computer displays, or roughly rectangular, as common for television images, and pixels are generally uniform in size and arrangement in an image. Other pixel geometries have been discussed in the art, but these are not commonly used. The interpolation methods discussed herein can be adapted to these alternate geometries.
It is also known in the art that digital images can be encoded in a two-dimensional x, y array with a single value at each location. Single-value encoding is often used for gray-scale images, but may also be used for various compressed color images.
Color images are commonly encoded in a three-dimensional array, with three values at every x, y location. These three values can denote primary color values, such as red, green, and blue (RGB) or cyan, magenta, and yellow (CMY). Three values can also denote luminance and color difference values such as YIQ; or can denote hue, saturation, and luminance value (HSV). It is also known in the art to use a color mosaic pattern (such as the Bayer pattern) to encode a color image in a two-dimensional image plane. Similar encoding can also be used to represent infra-red or x-ray images.
In some image processing systems, image manipulations are accomplished assuming that all of the original pixels are point values, located at the centers of the pixels. Distances to new pixel locations are also determined with reference to point values. More complex image processing tasks may take into account the shape and dimensions of individual pixels when performing image processing functions.
[1] J. A. Parker, R. V. Kenyon and D. E. Troxel, xe2x80x9cComparison of Interpolating Methods for Image Resamplingxe2x80x9d, IEEE Tran. Med. Imaging, 1983, vol. 2, No. 1, pp. 31-9, March 1983.
[2] N. A. Dodgson, xe2x80x9cQuadratic Interpolation for Image Resamplingxe2x80x9d, IEEE Transactions on Image Processing, vol. 6, No. 9, p. 6, September 1997.
[3] H. C. Ting and H. M. Hang, xe2x80x9cSpatially adaptive interpolation of digital images using fuzzy inferencexe2x80x9d, Proc. SPIExe2x80x94Int. Soc. Opt. Eng. (USA), Proceedings of the SPIExe2x80x94The International Society for Optical Engineering, vol. 2727, pt. 3, pp. 1206-17, March 1996.
[4] J. Allebach and P. W. Wong, xe2x80x9cEdge-Directed Interpolationxe2x80x9d, Proc. ICIP-96, IEEE Press, Lausanne CH, vol. I, pp. 707-10, 1996.
[5] Biancardi, L. Lombardi and V. Pacaccio, xe2x80x9cImprovements to image magnificationxe2x80x9d, Image Analysis and Proceeding. 9th International Conference, ICIAP xe2x80x297 Proceedings, p. 2 vol. (xxii+722+794), pp. 142-9 vol. 1, 1997.
[6] S. Thurnhofer and S. K. Mitka, xe2x80x9cEdge-enhanced image zoomingxe2x80x9d, Optical Engineering, vol. 35, No. 7, pp. 1862-70, SPIE Proc. European Signal Processing Conference, Grenoble, France, pp. 1445-8, July 1996.
[7] F. Michaud, C. T. Le Dinh and G. Lachiver, xe2x80x9cFuzzy Detection of Edge-Direction for Video Line Doublingxe2x80x9d, IEEE Transactions on Circuits and Systems for Video Technology, vol. 7, No. 3, pp. 539-42, June 1997.
Specific embodiments of the present invention address a number of problems associated with prior art systems. According to various specific embodiments, the present invention:
(1) provides a simple method that can up-scale an image in various scale ratios, including fractional scaling ratio, and can yield a sharp image with reduced unpleasant visual artifacts. The invention yields much better results compared with simple prior art methods and with some high complexity prior art methods.
(2) uses a power weight function that is gradient dependent and uses a function that has a linear dependence on the distance. A prior art solution, such as [3], instead develops a second correction phase that requires much higher complexity. In addition, [3] and some other known methods are not suitable for fractional scaling ratios.
(3) uses a power in the weight function that can be adapted according to the local contrast of edges to treat differently the high contrast edges and the low contrast edges.
A further understanding of the invention can be had from the detailed discussion of specific embodiments below. For purposes of clarity, this discussion refers to devices, methods, and concepts in terms of specific examples. However, the method of the present invention may operate with a wide variety of types of digital devices. It is therefore intended that the invention not be limited except as provided in the attached claims.
Furthermore, it is well known in the art that logic systems can include a wide variety of different components and different functions in a modular fashion. Different embodiments of a system can include different mixtures of elements and functions and may group various functions as parts of various elements. For purposes of clarity, the invention is described in terms of systems that include many different innovative components and innovative combinations of components. No inference should be taken to limit the invention to combinations containing all of the innovative components listed in any illustrative embodiment in the specification, and the invention should not be limited except as provided in the embodiments described in the attached claims.
All publications, patents, and patent applications cited herein are hereby incorporated by reference in their entirety for all purposes.
The invention will be better understood with reference to the following drawings and detailed description.